package leetcode.problems;

/**
 * Created by Administrator on 2018/3/20.
 */
public class _0320test {
    /*767. Reorganize String
    Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.
    If possible, output any possible result.  If not possible, return the empty string.
        Example 1:
    Input: S = "aab"
    Output: "aba"
    Example 2:
    Input: S = "aaab"
    Output: ""
    Note:
    S will consist of lowercase letters and have length in range [1, 500].

    给定一个字符串s，检查这些字母是否可以重新排列成两个相邻字符不一样的序列。
    如果可能的话，输出任何可能的结果。如果不可能，返回空字符串。
    例1：
    Input: S = "aab"
    Output: "aba"
    Example 2:
    Input: S = "aaab"
    Output: ""
    注：
    s由小写字母组成，长度为[1, 500]。


    class Solution {
        public String reorganizeString(String S) {
            // Create map of each char to its count
            Map<Character, Integer> map = new HashMap<>();
            for (char c : S.toCharArray()) {
                int count = map.getOrDefault(c, 0) + 1;
                // Impossible to form a solution
                if (count > (S.length() + 1) / 2) return "";
                map.put(c, count);
            }
            // Greedy: fetch char of max count as next char in the result.
            // Use PriorityQueue to store pairs of (char, count) and sort by count DESC.
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
            for (char c : map.keySet()) {
                pq.add(new int[] {c, map.get(c)});
            }
            // Build the result.
            StringBuilder sb = new StringBuilder();
            while (!pq.isEmpty()) {
                int[] first = pq.poll();
                if (sb.length() == 0 || first[0] != sb.charAt(sb.length() - 1)) {
                    sb.append((char) first[0]);
                    if (--first[1] > 0) {
                        pq.add(first);
                    }
                } else {
                    int[] second = pq.poll();
                    sb.append((char) second[0]);
                    if (--second[1] > 0) {
                        pq.add(second);
                    }
                    pq.add(first);
                }
            }
            return sb.toString();
        }
    }*/
}
